package LeetCode.leetcode39;

import java.util.ArrayList;
import java.util.List;

public class Review1 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        backTracking(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }
    public void backTracking(List<List<Integer>> res, ArrayList<Integer> path, int[] candidates, int target, int sum, int i){
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int j = i; j < candidates.length; j++){
            path.add(candidates[j]);
            sum += candidates[j];
            backTracking(res, path, candidates, target, sum, j);
            path.remove(path.size() - 1);
            sum -= candidates[j];
        }
    }
}
